package com.example.demo.leetcode.classics150;

/**
 * ******************************************************
 *
 * @author liugh9
 * @version 1.0
 * @classname _66分隔链表
 * @description
 * @date 2023/07/29 10:09
 * <p>
 * ******************************************************
 */
public class _66分隔链表 {

    public ListNode partition(ListNode head, int x) {
        ListNode dummy1 = new ListNode(-1), p = dummy1;
        ListNode dummy2 = new ListNode(-1), q = dummy2;

        while (head != null) {
            if (head.val < x) {
                p.next = head;
                p = p.next;
            } else {
                q.next = head;
                q = q.next;
            }
            head = head.next;
        }
        q.next = null;
        p.next = dummy2.next;
        return dummy1.next;
    }


    public class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }
}
